﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    //动态规划：dp[i][j]表示在前i个货币选择，总和为j的最小货币数量
    //动态转移方程：dp[i][j] = min(dp[i - 1][j],dp[i][j - vec[i]])
    //初始化：dp[i][0] = 0，dp[0][j] = INT_MAX (j > 0)
    //填表顺序：从左往右，从上到下
    //返回值：dp[n][aim]
    int n, aim;
    cin >> n >> aim;

    vector<int> vec(n, 0);
    for (int i = 0; i < n; ++i)
    {
        cin >> vec[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(aim + 1, 0x3f3f3f3f));
    // for(int i = 1; i < aim + 1; ++i)
    // {
    //     dp[0][i] = 0x3f3f3f3f;
    // }

    for (int i = 0; i < n + 1; ++i)
    {
        dp[i][0] = 0;
    }

    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 0; j < aim + 1; ++j)
        {
            // dp[i][j] = min(dp[i-1][j],j >= vec[i - 1] ? dp[i][j - vec[i - 1]] + 1 : 0x3f3f3f3f);//这条动态转移方程说明了在dp表的初始化中，最好全部初始化为0x3f3f3f3f，因为值不存在时，要根据题意，初始化为最大值或者最小值
            dp[i][j] = dp[i - 1][j];
            if (j >= vec[i - 1])
            {
                dp[i][j] = min(dp[i][j], dp[i][j - vec[i - 1]] + 1);
            }
        }
    }

    if (dp[n][aim] != 0x3f3f3f3f)
        cout << dp[n][aim] << endl;
    else
        cout << -1 << endl;
    return 0;
}

/*
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，
每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，
求组成aim的最少货币数。
如果无解，请返回-1.

数据范围：数组大小满足
0≤n≤10000，数组中每个数字都满足0<val≤10000，0≤aim≤5000
要求：时间复杂度O(n×aim) ，空间复杂度O(aim)。

输入描述：
第一行给定两个正整数分别是 n 和 aim 分别表示数组 arr 的长度和要找的钱数。
第二行给定 n 个正整数表示 arr 数组中的所有元素
输出描述：
输出组成 aim 的最少货币数

示例1
输入：
3 20
5 2 3
输出：
4
说明：
最少用四个 5 元凑成 20 元
*/

